package com.hqq.search.union_find;

/**
 * QuickFind
 * 一般的并查集数据结构
 * 合并两个节点时将第二个节点的下标设置成第一个节点的下标
 * 时间复杂度是n^2
 * Created by heqianqian on 2017/8/2.
 */
public class QuickFind implements UnionApi {

    /**
     * 节点数组
     */
    private int[] idArray;

    /**
     * 当前节点个数
     */
    private int count;

    /**
     * 初始化节点数组
     */
    public QuickFind(int count) {
        this.count = count;
        idArray = new int[count];
        for (int i = 0; i < count; i++) {
            idArray[i] = i;
        }
    }

    @Override
    public void union(int p, int q) {
        int pIndex = idArray[p];
        int qIndex = idArray[q];
        if (isConnected(p, q)) {
            return;
        }
        for (int i = 0; i < idArray.length; i++) {
            //将所有和p联通的节点的下标设置成p
            if (idArray[i] == pIndex) {
                idArray[i] = qIndex;
            }
        }
        count--;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return idArray[p] == idArray[q];
    }

    @Override
    public int find(int p) {
        return idArray[p];
    }

    @Override
    public int count() {
        return count;
    }

    @Override
    public int[] getArray() {
        return idArray;
    }
}
